def find_median(A, B, lo, hi):
    n = len(A)
    if hi - lo <= 0: return None
    k = (lo + hi) // 2
    left = B[n-k-2] if n-k-2 >=0 else -1
    rigt = B[n-k-1]
    if left <= A[k] <= rigt:
        return A[k]
    elif A[k] > rigt:
        return find_median(A, B, lo, k)
    else:
        return find_median(A, B, k + 1, hi)

def two_array_median(A, B):
    n = len(A)
    med = find_median(A, B, 0, n)
    if med is None:
        med = find_median(B, A, 0, n)
    return med

if __name__=='__main__':
    A = [0,0,0,0,9,9]
    B = [1,2,3,4,5,6]
    print two_array_median(A, B)
